数学的枠組み
核心的な目的は、線形結合 $Ax = x_1a_1 + \dots + x_na_n$ が $b$ を最もよく近似するようなベクトル $x \in \mathbb{R}^n$ を見つけることです。これはしばしば $b$ を回帰因子（$A$ の列）へ回帰する （$A$ の列）。
我々は残差ベクトル $r = Ax - b$ に注目します。実際には、 過剰決定系 ここで $m > n$ であると仮定します。なぜなら、$m = n$ かつ $A$ が正則の場合、最適解は単に $A^{-1}b$ となり、誤差はゼロになるため、最適化の文脈では自明なケースになってしまうからです。
代表的な変種
ペナルティを与えるべき誤差の「種類」によって、異なるノルムを選択します：
最も一般的な手法です。残差の二乗和を最小化します：$\|Ax - b\|_2^2$。大きな外れ値に対して敏感ですが、正規方程式により解析的な解が得られます。
最大の 絶対誤差 $\max_i |r_i|$ を最小化します。すべての測定値が厳密な許容範囲内に収まる必要がある場合に使用されます。次の線形計画法（LP）で解くことができます： 絶対誤差 $\max_i |r_i|$ を最小化します。すべての測定値が厳密な許容範囲内に収まる必要がある場合に使用されます。次の線形計画法（LP）で解くことができます：
目的関数：$t$ の最小化
制約条件：$-t\mathbf{1} \preceq Ax - b \preceq t\mathbf{1}$
残差の絶対値の和 $\sum |r_i|$ を最小化します。誤差を二乗しないため、外れ値に対して強い特徴があります。また、線形計画法（LP）でも解けます：
目的関数：$\mathbf{1}^T t$ の最小化
制約条件：$-t \preceq Ax - b \preceq t$
推定の文脈
多くの工学分野において、真の状態 $x$ がノイズによって隠蔽されていると仮定します：$y = Ax + v$。我々の目的は、推定値 $\hat{x} = \text{argmin}_z \|Az - y\|$ を求めるところです。ノルムを選択することは、ノイズ $v$ の統計的分布についての仮定をしていることに等しいのです。